Introduction

Two-factor authentication is ubiquitous in contemporary authentication systems. One of the methods used for 2FA are the so-called authenticator apps. Whenever the server needs to validate that it really is you who is trying to log in, you just open the app and it magically produces a code which you can enter and the server magically accepts it! Furthermore, a new code appears after a given period of time, usually 30-60 seconds.

But how does the authenticator app know what code to give and how does the server know when the code is correct?

One-Time Passwords

The code generated by the authenticator app is called a one-time password. Whenever you set up 2FA on your account for the first time, you will be asked to either scan a QR code with the application or manually enter an alphanumeric string into the authenticator application, called a seed, which is then stored on both the server and in your authenticator app. This seed should never be shared with anyone else.

From then on, one-time passwords are generated using a pseudorandom function generator (PRFG). One example procedure for a one-time password authentication uses a publicly known one-bit PRFG . Whenever you log in, the server sends a random base index , which is an integer between and inclusively, and a security parameter . Your authenticator app then uses the secret seed and the PRFG to generate bits, starting from the base index the server provided. The one-time password is then simply the concatenation of the bits . This resulting binary string can be converted into a decimal number so that it is easy for a human, i.e. you, to write it in the prompt on the log-in page.

When the server receives your code, it generates its own code by using the secret seed , the same base index and the same security parameter . It then compares its own code with the code you sent and if they match, you are authenticated. Since both used the exact same base index and security parameter, the only way for your code to match the server's is if you also used the same secret seed , thus proving your authenticity.

In practice, one-time password systems use PRFGs which output more than a single bit.

Security of One-Time Passwords

What does it mean for a one-time password system to be secure? Well, the server either rejects or accepts your log in depending on the code you sent it. An adversary won't have access to the secret seed, so the most basic strategy, which is always possible to do, is to attempt to guess the code. The probability of the adversary just guessing the code is , since there are a total of possible codes. This motivates the following definition of security for one-time passwords.

A one-time password system with a seed $s$ of length $S$, base index $i_0 \in \{0,1,..., 2^S - 1\}$ and security parameter $l$ is *secure* if for every efficient adversary $\textit{Eve}(i_0: \textbf{int}[0..2^S], l: \textbf{int}) \to \textbf{str}[l]$ who knows the base index and the security parameter, the probability that $\textit{Eve}$ will be authenticated by the server without knowledge of the secret seed is at most $\frac{1}{2^l} + \epsilon(S)$ for some neglgigible $\epsilon$, i.e.

$$\Pr[\textit{Server}(\textit{Eve}(i_0, l)) = \text{ authenticated }] \le \frac{1}{2^l} + \epsilon(S)$$

A one-time password system is secure if there is no adversary that, given the base index $i_0$ and security parameter $l$, can guess what code the server will generate with probability marginally better than $\frac{1}{2^l}$.

From this definition we see that the security of a one-time password heavily depends on the security of the parameter . If security is to be achieved, the security parameter must be at most as long as the seed, i.e. . Otherwise, an adversary can attempt to simply guess the seed with probability . Since the seed would be shorter than the security parameter, there would be fewer possible seeds than possible codes and would be non-negligibly greater than . However, making the security parameter short, i.e. , is also unreasonable since it would increase the overall likelihood that an adversary guesses the code. Ergo, the Goldilocks value for the security parameter is the length of the seed, i.e. .

Indeed, using this definition, we can prove that the aforementioned one-time password system is secure so long as the PRFG it uses is.

TODO

Replay Attacks

It is paramount that the same base index is never used twice in order to thwart replay attacks. If an adversary eavesdrops on the connection between you and the server, they can store the base index and the code you send to the server in every two-factor authentication session.

The adversary can later try to authenticate and if the server sends them a base index which they previously recorded from you, then they also know the correct code for this index and will successfully authenticate.

The same base index should never be reused.

A random base index is just a fairly easy way to achieve this non-repetition of indices because even if the index is just 128 bits in length, the probability that the same index will be reused is , which is ridiculously low.